package com.base.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * TODO(390. 消除游戏)
 * 列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
 *
 * 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
 * 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
 * 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
 * 给你整数 n ，返回 arr 最后剩下的数字。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/elimination-game
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author leon
 * @date 2022年01月03日 18:37
 */
public class LastRemaining {
    /**
     * 遍历法；超时
     * @param n
     * @return
     */
    public int lastRemaining(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        // 1代表正方向，-1代表负方向
        while (true){
            if(list.size()==1){
                break;
            }
            int j = 0;
            // 左移动
            while (j<list.size()){
                if (list.size()<=1){
                    break;
                }
                list.remove(j);
                j+=1;
            }
            j = list.size()-1;
            while (j>=0){
                if (list.size()<=1){
                    break;
                }
                list.remove(j);
                j-=2;
            }
            if (list.size()<=1){
                break;
            }
        }
        return list.get(0);
    }

    //    约瑟夫环
    public int lastRemaining1(int n) {
        return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
    }

//    作者：AC_OIer
//    链接：https://leetcode-cn.com/problems/elimination-game/solution/gong-shui-san-xie-yue-se-fu-huan-yun-yon-x60m/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    public static void main(String[] args) {
        System.out.println(new LastRemaining().lastRemaining(9));
    }
}
